Như là thuộc địa đầu tiên của người châu Âu theo đạo Thiên chúa thiết lập với mục đích thương mại ở khu vực Đông Nam Á, nó được bao quanh bởi nhiều vương quốc Hồi giáo bản địa mới nổi. Ngoài ra, với sự tác động thù địch ban đầu với chính sách của người Malay địa phương, Malacca thuộc Bồ Đào Nha phải đối mặt với sự thù địch nghiêm trọng. Họ phải hứng chịu trong nhiều năm các trận đánh bắt đầu bởi các Sultan Malay, những người muốn thoát khỏi người Bồ Đào Nha và đòi lại đất đai của họ. Mahmud đã có nhiều nỗ lực để chiếm lại thủ đô. Mahmud nhận thêm được sự hỗ trợ từ các đồng minh của mình là Vương quốc Hồi giáo Demak của người Java và năm 1511 đã đồng ý gửi lực lượng hải quân để hỗ trợ. Được dẫn dắt bởi Pati Unus, Quốc vương Demak, những nỗ lực Malay-Java kết hợp nhưng có kết quả thất bại. Người Bồ Đào Nha chống trả và buộc vua phải chạy trốn để Pahang. Sau đó, vua đi thuyền tới Bintan và thành lập một thủ đô mới. Với nền tảng được củng cố, sultan tăng các lực lượng hỗn hợp Malay và tổ chức một số cuộc tấn công và phong tỏa đối với vị trí của Bồ Đào Nha. Cuộc tấn công thường xuyên nhắm vào Malacca gây ra những khó khăn nghiêm trọng đối với Bồ Đào Nha. Trong năm 1521, lần thứ hai Demak tiến hành chiến tranh để giúp sultan Malay chiếm lại Malacca. Tuy nhiên, một lần nữa chiến dịch lại thất bại với phí tổn ảnh hưởng đến cuộc sống riêng của Sultra Demak. Sau này ông được nhớ đến như Hoàng tử Sabrang Lor hay Hoàng tử vượt qua (Biển Java) để đến phương Bắc (bán đảo Mã Lai). Sau các cuộc tấn công đã làm người Bồ Đào Nha tin rằng các lực lượng của sultra đã buộc phải từ bỏ ý định tái chiếm Malacca. Nhiều lần người Bồ Đào Nha đã cố gắng để ngăn chặn các lực lượng Malay. Nhưng sau đó vào năm 1526, Bồ Đào Nha đã dành chiến thắng và tàn phá Bintan. Sultra Malay buộc phải rút về Kampar ở Riau, Sumatra. Nơi ông qua đời hai năm sau đó, ông để lại ngôi vị cho hai con trai: Muzaffar Shah và Alauddin Shah Riayat II.

Muzaffar Shah được đưa lên làm vua của người dân ở phía bắc của bán đảo để thành lập Vương quốc hồi giáo Perak. Trong khi con trai khác của Mahmud là Alauddin, kế thừa sự nghiệp của cha mình và thành lập một thủ đô mới ở miền Nam. Quyền bính của Ngài là Vương quốc Hồi giáo Johor, vương quốc kế thừa của Malacca.

Một số nỗ lực để loại bỏ ách thống trị Bồ Đào Nha khỏi Malacca đã được thực hiện bởi sultan Johor. Một yêu cầu gửi đến Java vào năm 1550 dẫn đến Nữ hoàng Kalinyamat, quan nhiếp chính của Jepara đã gửi cùng 4,000 binh sĩ trên 40 tàu để đáp ứng yêu cầu của sultan Johor để lấy Malacca. Quân của Jepara sau đó gia nhập lực lượng với liên minh Malay và được quản lý để hợp nhất với khoảng 200 tàu chiến cho cuộc tấn công sắp tới vào Malacca. Lực lượng tấn công từ phía bắc và chiếm được vùng đất rộng lớn của Malacca, nhưng Bồ Đào Nha đã trả đũa và đẩy lùi lực lượng tấn công. Lực lượng liên minh Mã Lai trên các tàu bị đẩy trở ra biển, trong khi lực lượng của Jepara vẫn trên bờ và buộc rút lui sau khi các chỉ huy bị sát hại. Cuộc chiến tiếp tục diễn ra trên các bờ biển và trên biển kết quả làm hơn 2,000 binh sĩ Jepara bị giết. Một cơn bão mắc kẹt hai tàu Jepara trên bờ biển Malacca và họ đã trở thành nạn nhân cho Bồ Đào Nha. Chỉ ít hơn một nửa trong số lực lượng Jepara có thể rút khỏi Malacca.

Trong năm 1567, Hoàng tử Husain Ali I Riayat Syah từ Vương quốc Hồi giáo Aceh đã phát động một cuộc tấn công của hải quân để lật đổ người Bồ Đào Nha từ Malacca, nhưng điều này lại một lần nữa kết thúc trong thất bại. Năm 1574 một cuộc tấn công kết hợp từ Vương quốc Hồi giáo Aceh và Java Jepara cố gắng một lần nữa để giành lại Malacca từ Bồ Đào Nha, nhưng đã kết thúc trong thất bại do sự phối hợp kém.

Cạnh tranh từ các cảng khác như Johor làm cho các thương gia châu Á không còn neo ở Malacca nên thành phố bắt suy thoái.[3] Thay vì đạt tham vọng chiếm lĩnh mạng lưới thương mại châu Á, người Bồ Đào Nha thực sự gây nên một mớ hỗn độn. Thay vì một thành lập trung tâm thành phố trao đổi của châu Á giàu có, hay một sự kiểm soát của nhà nước Malay ở eo biển làm cho an toàn hơn trong hàng hải thương mại, Bồ Đào Nha đã làm buôn bán rải rác ở các cảng khác nhau và các cuộc chiến khốc liệt ở eo biển Malacca[3].